#include <iostream>
#include <vector>
#include <algorithm>
#define INT_MAX 10000
using namespace std;

//求：有向无环图的单源最短路径
//算法1：将有向无环图【拓扑排序】得到拓扑排序序列
//算法2：动规求最短路径

int dag_short_path(vector<vector<int> > &dag, int n){
    //形参dag是一个拓扑排序序列
    //求从排序序列中的第0个点到第t个点的长度，从0开始计数
    int dp[n];
    fill(dp, dp + n, INT_MAX);
    dp[0] = 0;
    dp[1] = dag[0][1];
    for (int i = 2; i < n; i++) {
        for (int j = 0; j < i; j++) {    
            dp[i] = min(dp[i], dp[j] + dag[j][i]);
        }
    }
    return dp[n-1];
}

int main(){
    // 有 6 个顶点
    int n = 6;
    // 表示拓扑排序序列
    vector<int> point1 = {0, 1, 1, INT_MAX, INT_MAX, INT_MAX};
    vector<int> point2 = {INT_MAX, 0, 3, 4, 6, INT_MAX};
    vector<int> point3 = {INT_MAX, INT_MAX, 0, 5, 6, INT_MAX};
    vector<int> point4 = {INT_MAX, INT_MAX, INT_MAX, 0, 7, 8};
    vector<int> point5 = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, 9};
    vector<int> point6 = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0};
    vector<vector<int> > dag;
    dag.push_back(point1);
    dag.push_back(point2);
    dag.push_back(point3);
    dag.push_back(point4);
    dag.push_back(point5);
    dag.push_back(point6);
    cout << dag_short_path(dag, n) << endl;

    return 0;
}